package com.LeeCode;

import java.util.Arrays;

/**
 * 下一个排列
 */

public class Code031 {
    public static void main(String[] args) {
        int[] nums = {3, 2, 1};
        new Code031().nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void nextPermutation(int[] nums) {
        int turnOver = nums.length - 2;
        while (turnOver >= 0) {
            if (nums[turnOver] < nums[turnOver + 1]) {
                break;
            }
            turnOver--;
        }
        if (turnOver >= 0) {
            int change = nums.length - 1;
            while (change > turnOver && nums[turnOver] >= nums[change]) {
                change--;
            }
            int temp = nums[turnOver];
            nums[turnOver] = nums[change];
            nums[change] = temp;
        }
        int left = turnOver + 1, right = nums.length - 1;
        while (left < right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            left++;
            right--;
        }
    }
}
